import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution47 {

    public static void main(String args[]) {
        Solution47 s = new Solution47();
        System.out.println(s.permuteUnique(new int[]{1, 1, 2}));
    }

    HashMap<List<Integer>, Integer> mp;
    List<List<Integer>> ret;

    public List<List<Integer>> permuteUnique(int[] nums) {
        mp = new HashMap<>();
        ret = new ArrayList<>();
        dfs(0, nums);
        return ret;
    }

    public void dfs(int idx, int[] nums) {
        if (idx == nums.length) {
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                l.add(nums[i]);
            }
            ret.add(l);
            return;
//            if (!mp.containsKey(l)) {
//
//                mp.put(l, 1);
//                return;
//            }
        }
        HashMap<Integer, Integer> mp = new HashMap<>();
        for (int i = idx; i < nums.length; i++) {
            if (!mp.containsKey(nums[i])) {
                swap(nums, i, idx);
                dfs(idx + 1, nums);
                swap(nums, idx, i);
                mp.put(nums[i], 1);
            }
        }
    }

    public void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}
